1. Field of the Invention
This invention relates generally to minicomputing systems and more particularly to storage hierarchies having high speed low capacity storage devices and lower speed high capacity storage devices coupled in common to a systems bus.
2. Description of the Prior Art
The storage hierarchy concept is based on the phenomena that individual stored programs under execution exhibit the behavior that in a given period of time a localized area of memory receives a very high frequency of usage. Thus, a memory organization that provides a relatively small size buffer at the CPU interface and the various levels of increasing capacity slower storage can provide an effective access time that lies somewhere in between the range of the fastest and the slowest elements of the hierarchy and provides a large capacity memory system that is "transparent" to the software.
Prior art was limited to storing the requested data word with its address in hardware registers. When the need came about for expanded size, low cost buffers, the prior art utilized a block organization. If a particular word was requested by the CPU, the block containing that word was stored in a high speed data buffer. This had the disadvantage of bringing into the high speed buffer words with a relatively low probability of usage. Assuming a four word block, if word 4 is requested, the entire block including words 1, 2 and 3 which may have a relatively low probability of usage, are brought into the high speed buffer. To optimize the usage of the memory hierarchy, the operating system must organize memory in such a manner that software submodules and data blocks start with word 1 of the block. To overcome this difficulty, the prior art utilized a "block lookahead". When one block was in the high speed buffer, a decision was made during the processing of a data word in that block to bring the next block into the high speed buffer.
U.S. Pat. No. 3,231,868 issued to L. Bloom, et al., entitled "Memory Arrangement for Electronic Data Processing System" discloses a "look aside" memory which stores a word in a register and its main memory address in an associated register. To improve performance, U.S. Pat. No. 3,588,829, issued to L. J. Boland, et al., discloses an eight-word block fetch to the high speed buffer from main memory if any word in the eight-word block is requested by the CPU.
An article by C. J. Conti, entitled "Concepts for Buffer Storage" published in the IEEE Computer Group News, March 1969, describes the transfer of the 64-byte blocks as used on the IBM 360/85 when a particular byte of that block not currently in the buffer is requested. The IBM 360/85 is described generally on pages 2 through 30 of the IBM System Journal, Vol. 71, No. 1., 1968.
U.S. Pat. No. 3,588,829 issued to Boland, et al., entitled "Integrated Memory system with Block Transfer to a Buffer Store" describes the prefetching of a block of information if a word in that block is requested.
U.S. Pat. No. 3,820,078 issued to Curley, et al., entitled "Multilevel Storage System Having A Buffer Store With Variable Mapping Modes" describes the transfer of blocks of 32 bytes or half-blocks of 16 bytes from main memory to the high speed buffer when a word (4 bytes) of the block or half-block is requested by the CPU. U.S. Pat. No. 3,896,419 issued to Lange, et al., entitled "Cache Memory Store In A Processor Of A Data Processing System" describes the transfer of a four word block from main memory to the high speed buffer when a word of that block is requested by the CPU. U.S. Pat. No. 3,898,624 issued to Tobias entitled "Data Processing System With Variable Prefetch and Replacement Algorithms" describes the prefetching of the next line (32 bytes) from main memory to the high speed buffer when a specific byte is requested by the CPU of the previous line.
In minicomputers, particularly those minicomputers which are organized in such a fashion that a plurality of system units are connected in common to a system bus, the prior art systems present a number of problems all having to do with reducing the throughput of the minicomputer. The prior art sends back to cache from main memory the entire block of words in which the requested word is located. This includes words with addresses preceding the requested word and words with addresses following the requested words. In most cases, the CPU will require on the following cycle the word in the next higher address. This results in words with high probability of being used as well as words with lower probability of being used being transferred into cache. To overcome this problem, the prior art requires that the programmer or the operating system optimize their programs to start sequences off with words at the first address of each block. Another problem in the prior art is that a block of words transferring from main memory to cache comes over in successive cycles, for example, a 32 byte block may be transferred in 8 cycles, 4 bytes at a time. In the minicomputer bus oriented system, this would greatly reduce the throughput of the system.